/**
  题目:
   给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5
  
  思路:
    找到中点 中序遍历
  
  效果:
    执行用时：8 ms, 在所有 Go 提交中击败了74.95%的用户
    内存消耗：6.1 MB, 在所有 Go 提交中击败了37.08%的用户
*/
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    a, b := &ListNode{}, &ListNode{}
    aa,bb := a,b
    for head != nil{
        if head.Val >= x{
            bb.Next = head
            bb = bb.Next
        }else if head.Val < x{
            aa.Next = head
            aa = aa.Next
        }
        head = head.Next
    }
    bb.Next = nil
    aa.Next = b.Next
    return a.Next
}
